package com.dataStructure.stack;

import com.dataStructure.Map.Entry;

import java.time.LocalDate;
import java.util.*;


/**
 *  单调队列  和  优先队列
 *  单调队列是维持队列内单调递增或者单调递减，但绝不是排序，他会进行删除（从队尾出队）
 *
 *  优先队列：则是取升序排列的第一位
 */


public class LeetCode {

    public static void main(String[] args) {
      topKFrequent(new int[]{1,1,1,2,2,3},2);
        Deque<Integer> queue3 = new LinkedList<Integer>();

        int j =0;
        for (; j < 4; j++) {
            if (j == 2) {
                break;
            }
        }
        System.out.println(j);


    }


    /**
     * 最短无序子数组
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        if (isSort(nums))
            return 0;

        int[] ar = Arrays.copyOf(nums, nums.length);
        Arrays.sort(ar);
        int left = 0;
        for (int i = 0; i < nums.length ;i++) {
            if (ar[i] != nums[i]) {
                left = i;
                break;
            }
        }
        int right = nums.length - 1;
        for (int i = nums.length- 1; i >= 0 ; i--) {
            if (ar[i] != nums[i]) {
                right = i;
                break;
            }
        }
        if (left == 0 && right == nums.length - 1) {
            return 0;
        }

        return right -left + 1;


    }

    private Boolean isSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }

        }
        return true;
    }

    /**
     * 每日温度
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ar = new int[temperatures.length];
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = temperatures.length - 1; i >= 0; i--) {
            int e = temperatures[i];
            while (!stack.isEmpty() && temperatures[stack.peek()] <= e) {
                stack.pop();
            }

            ar[i] = !stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);

        }

        return ar;
    }


    /**
     * 下一个更大元素 1
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] ar = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int e1 = nums1[i];
            int j = 0;
            int value = -1;
            for (; j < nums2.length; j++) {
                if (nums2[j] == e1) {
                    break;
                }
            }
            for (; j< nums2.length; j++) {
                if (nums2[j] > e1) {
                    value = nums2[j];
                    break;
                }
            }
            ar[i] = value;
        }
        return ar;
    }

    /**
     * 单调队列   力扣 239
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<Integer>();
        //放入前k个元素
        for (int i = 0 ;i < k; i++) {
            while (queue.size() != 0 && nums[i] > queue.peekLast()) {
                //将最后一个从对尾移除,入队时只维持一个大的值在对头
                queue.pollLast();
            }
            queue.offer(nums[i]);
        }
        list.add(queue.peek());

        for (int i = k ; i < nums.length; i++) {
            //删除滑动窗口
            if (queue.size() != 0 && nums[i - k] == queue.peek()) {
                queue.poll();
            }

            while (queue.size() != 0 && nums[i] > queue.peekLast()) {
                //将最后一个从对尾移除,入队时只维持一个大的值在对头
                queue.pollLast();
            }
            queue.offer(nums[i]);
            list.add(queue.peek());

        }
        int[] arrays = list.stream().filter(integer -> integer!=null).mapToInt(i->i).toArray();
        return arrays;


    }

    /**
     * 力扣347 前k个高频元素  yun yong duilie
     * @param nums  给定数组
     * @param k     频率
     */
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int e : nums) {
            if (map.get(e) == null) {
                map.put(e,1);
            }
            else if (map.get(e) != null) {
                map.put(e,map.get(e) + 1);
            }
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] > o2[1])
                    return -1;
                else
                    return 1;
            }
        });

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int[] ar = {entry.getKey(), entry.getValue()};
            queue.offer(ar);
        }
        while (queue.size() > k) {
            queue.poll();
        }

        int[] ints = new int[k];
        int i = 0;
        for (int[] e : queue) {
            ints[i] = e[0];
            i++;
        }
        return ints;
    }

    /**
     *  后缀表达式求值
     * @param tokens   给定表达式数组
     */
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (String e : tokens) {
            if (e.equals("+")) {
                int tow = stack.pop();
                int one = stack.pop();
                stack.push(one + tow);
            }
            else if (e.equals("-")) {
                int tow = stack.pop();
                int one = stack.pop();
                stack.push(one - tow);
            }
            else if (e.equals("*")) {
                int tow = stack.pop();
                int one = stack.pop();
                stack.push(one * tow);
            }
            else if (e.equals("/")) {
                int tow = stack.pop();
                int one = stack.pop();
                stack.push(one / tow);
            }
            else {
                stack.push(Integer.valueOf(e));
            }
        }

        return stack.peek();



    }

    /**
     * 力扣 1047. 删除字符串中的所有相邻重复项
     */
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (stack.isEmpty()) {
                stack.push(ch);
            }
            //栈存在元素
            else {
                if (stack.peek()  == ch) {
                    stack.pop();
                }
                else {
                    stack.push(ch);
                }
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (Character e : stack) {
            stringBuilder.append(e);
        }
        return stringBuilder.toString();

    }
    /**
     * 力扣 20 有效的括号
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char ch: s.toCharArray()) {
            if (!stack.isEmpty()) {
                if (ch == ')') {
                    if (stack.peek() == '(') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else if (ch == ']') {
                    if (stack.peek() == '[') {
                        stack.pop();
                    }  else {
                        return false;
                    }
                }   else if (ch == '}') {
                    if (stack.peek() == '{') {
                        stack.pop();
                    }  else {
                        return false;
                    }
                } else {
                    stack.push(ch);
                }
            } else {
                stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
}

/**
 *双栈实现队列
 */
class Queue {
    private static LinkedList<Integer> stackPut = new LinkedList<>();
    private static LinkedList<Integer> stackTake = new LinkedList<>();



    public static void enqueue(int x) {
        stackPut.push(x);
    }

    public static int poll() {
        if (!stackTake.isEmpty()) {
            return stackTake.pop();
        }

        else {
           while (!stackPut.isEmpty()) {
               stackTake.push(stackPut.pop());
           }

           if (stackTake.isEmpty()) {
               return -1;
           }
           return stackTake.pop();

        
        }
    }
}
